package cn.aylog.algorithm;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        // int arr[] = {8,9,1,7,2,3,5,4,6,0};
        // insertSort(arr);
        // Arrays.stream(arr).forEach(i -> System.out.printf("%d ", i));
        int len = 800000;
        int[] arr = new int[len];
        for(int i=0; i<len; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        insertSort(arr); // 609 625
        long end = System.currentTimeMillis();
        System.out.println("insertSort耗时: " + (end - start));
    }

    public static void insertSort(int arr[]) {
        int len = arr.length;
        int insertVal, index;
        long cnt = 0;
        for(int x=1; x<len; x++) { // 1 3 2
            // if(arr[x] > arr[x - 1]) {
            //     continue;
            // }
            insertVal = arr[x];
            index = x - 1;
            while(index >= 0 && insertVal < arr[index]) {
                cnt++;
                // 数据后移
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index+1] = insertVal;
        }
        System.out.println("cnt = " + cnt);
    }

}
